﻿using System;
using System.Collections.Generic;

namespace Heaven.Mathematics.Algorithms
{
    /// <summary>
    /// LZ77 is the lossless data compression algorithms published 
    /// in papers by Abraham Lempel and Jacob Ziv in 1977. LZ77 algorithms 
    /// achieve compression by replacing portions of the data with references 
    /// to matching data that has already passed through both encoder and decoder. 
    /// A match is encoded by a pair of numbers called a length-distance pair, 
    /// which is equivalent to the statement "each of the next length 
    /// characters is equal to the character exactly distance 
    /// characters behind it in the uncompressed stream.
    /// Class can compress up to 2GB, but 
    /// it would be required a lot of memory
    /// </summary>
    public class LempelZiv
    {
        #region Compressing

        /// <summary>
        /// Compresses the given data
        /// </summary>
        /// <param name="data">Original data</param>
        /// <returns>Compressed data</returns>
        public static byte[] Compress(byte[] data)
        {
            // Case of small amount of data
            if (data.Length == 0) return new byte[] { 0, 0, 0, 0 };
            if (data.Length < 3)
            {
                byte[] len = BitConverter.GetBytes((UInt32)data.Length);
                byte[] res = new byte[data.Length + 5];
                res[0] = len[0];
                res[1] = len[1];
                res[2] = len[2];
                res[3] = len[3];
                res[4] = 0; // Control byte
                for (int i = 0; i < data.Length; i++)
                {
                    res[i + 5] = data[i];
                }
                return res;
            };

            // Convention:
            // Minimum length of data from dictionary 
            // is 3 bytes, so 0 equals 3, 1 equals 4, etc.
            // Length-distance pair is as 12 bit distance / 4 bit length
            // So maximum distance is 4095, lenght is 15+3=18

            // Current control byte (which contains 00010010, 
            // where 0 is an unconpresses byte, 
            // 1 is a length-distance pair)
            int controlByte = 4;
            // Current contol bit points to 
            // bit in the current control byte
            int currentControlBit = 3;
            // Current position 
            int currentSourcePosition = 3;
            int currentCompressedPosition = 8;

            // Compressed data
            byte[] compressed = new byte[(int)(data.Length * 1.4) + 20];

            // Write size of original data
            byte[] size = BitConverter.GetBytes((UInt32)data.Length);
            compressed[0] = size[0];
            compressed[1] = size[1];
            compressed[2] = size[2];
            compressed[3] = size[3];
            compressed[4] = 0; // Control byte

            // Copy first tree items
            compressed[5] = data[0];
            compressed[6] = data[1];
            compressed[7] = data[2];

            int windowFirstItem = 0;
            int windowLastItem = 2;
            List<int>[] window = new List<int>[256];
            for (int i = 0; i < 256; i++) window[i] = new List<int>(32);
            window[data[0]].Add(0);
            window[data[1]].Add(1);
            window[data[2]].Add(2);

            // LZ77 algorithm starts
            while (currentSourcePosition < data.Length)
            {
                // Find max equal sequence of bytes
                int maxFindLength = 0;
                int maxLengthDistance = 0;

                // Bytes to the end of the source
                int maxfurfer = Math.Min(18, data.Length - currentSourcePosition - 1);

                // Find RLE potential
                /*for (int i = 0; i < maxfurfer; i++)
                {
                    if (data[currentSourcePosition - 1] == data[currentSourcePosition + i])
                    {
                        if (maxFindLength < i + 1)
                        {
                            maxFindLength = i + 1;
                            maxLengthDistance = 1;
                        }
                    }
                    else break;
                }*/

                // Find max equal part in the window
                foreach (int index in window[data[currentSourcePosition]])
                {
                    if (maxFindLength == maxfurfer) break;

                    int length = Math.Min(maxfurfer, currentSourcePosition - index - 1);

                    for (int i = 1; i < length; i++)
                    {
                        if (data[index + i] == data[currentSourcePosition + i])
                        {
                            if (maxFindLength < i + 1)
                            {
                                maxFindLength = i + 1;
                                maxLengthDistance = currentSourcePosition - index;
                            }
                        }
                        else break;
                    }
                }

                if (maxFindLength >= 3)
                {
                    // Update the control bit
                    compressed[controlByte] |= (byte)((byte)1 << currentControlBit);

                    // Push a length-distance pair
                    ushort temp = (ushort)(maxLengthDistance);
                    temp |= (ushort)((ushort)(maxFindLength - 3) << 12);
                    compressed[currentCompressedPosition + 0] = (byte)temp;
                    compressed[currentCompressedPosition + 1] = (byte)((temp & 0xFF00) >> 8);
                    currentCompressedPosition += 2;

                    // Add new bytes to the window
                    for (int i = currentSourcePosition; i < currentSourcePosition + maxFindLength; i++)
                    {
                        window[data[i]].Add(i);
                        windowLastItem++;
                    }
                    // Shift position in original data as well
                    currentSourcePosition += maxFindLength;
                    // Shift the sliding window
                    while (windowLastItem - windowFirstItem >= 4095)
                    {
                        // Remove 
                        window[data[windowFirstItem]].Remove(windowFirstItem);
                        windowFirstItem++;
                    }

                }
                else
                {
                    // Push one uncompressed byte
                    compressed[currentCompressedPosition] = data[currentSourcePosition];
                    currentCompressedPosition++;

                    // Add byte
                    window[data[currentSourcePosition]].Add(currentSourcePosition);
                    windowLastItem++;

                    // Shift position in original data as well
                    currentSourcePosition++;

                    // Shift the sliding window
                    if (windowLastItem - windowFirstItem >= 4095)
                    {
                        // Remove 
                        window[data[windowFirstItem]].Remove(windowFirstItem);
                        windowFirstItem++;
                    }

                    // Also we need to write zero to 
                    // control byte, so do nothing
                }

                // Shift the control bit
                currentControlBit++;
                currentControlBit %= 8;
                if (currentControlBit == 0)
                {
                    // Make a new control byte
                    controlByte = currentCompressedPosition;
                    currentCompressedPosition++;
                }
            }

            byte[] result = new byte[currentCompressedPosition];
            Array.Copy(compressed, result, currentCompressedPosition);
            return result;
        }

        #endregion

        #region Decompressing

        /// <summary>
        /// Decompresses the given data
        /// </summary>
        /// <param name="compressed">Compressed data</param>
        /// <returns>Original data</returns>
        public static byte[] Decompress(byte[] compressed)
        {
            // Extract length of original data and allocate memory
            byte[] uncompressed = new byte[BitConverter.ToUInt32(
                new byte[] { 
                    compressed[0], 
                    compressed[1], 
                    compressed[2], 
                    compressed[3] }, 0)];

            // Current control byte (which contains 00010010, 
            // where 0 is an unconpresses byte, 
            // 1 is a length-distance pair)
            byte controlByte = 0;
            // Current positions
            int currentUncompressedPosition = 0;
            int currentCompressedPosition = 4;

            while (uncompressed.Length != currentUncompressedPosition)
            {
                // Move to next control byte
                controlByte = compressed[currentCompressedPosition];
                currentCompressedPosition++;

                // Read the control byte
                for (int i = 0; i < 8; i++)
                {
                    byte iscompressed = (byte)((controlByte >> i) & 1);

                    if (iscompressed != 0)
                    {
                        ushort temp = BitConverter.ToUInt16(new byte[] {
                            compressed[currentCompressedPosition + 0],
                            compressed[currentCompressedPosition + 1] }, 0);
                        ushort distance = (ushort)(temp & 0x0FFF);
                        ushort length = (ushort)(((temp & 0xF000) >> 12) + 3);

                        for (int j = 0; j < length; j++)
                        {
                            uncompressed[currentUncompressedPosition + j] = uncompressed[currentUncompressedPosition - distance + j];
                        }

                        currentUncompressedPosition += length;
                        currentCompressedPosition += 2;
                    }
                    else
                    {
                        uncompressed[currentUncompressedPosition] = compressed[currentCompressedPosition];
                        currentUncompressedPosition++;
                        currentCompressedPosition++;
                    }

                    if (uncompressed.Length == currentUncompressedPosition) break;
                }
            }

            return uncompressed;
        }

        #endregion
    }
}
